package com.duing.listnode;

import java.util.HashMap;

public class LRUCache1 {
    // 底层存储的容器
    private HashMap<Integer, DListNode> map;

    // 容量
    private int capacity;
    // 实际使用的大小
    private int size;
    // 声明 空的头节点和尾节点
    private DListNode head, tail;

    class DListNode {
        int key;
        int value;
        DListNode prev, next;

        public DListNode() {
        }

        public DListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache1(int capacity) {
        this.capacity = capacity;
        this.size = 0;

        map = new HashMap<>(capacity);
        //head = new DListNode(-1,-1);
        head = new DListNode();
        //tail = new DListNode(10000,10000);
        tail = new DListNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DListNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 为了保持有序 将当前节点移动到头部
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 先判断 元素是否存在  如果存在 更新value
        // 如果不存在  插入新元素  是否超出容量
        DListNode node = map.get(key);
        if (node != null) {
            node.value = value;
            // 更新了key的使用频率  重新排序  将当前节点移动到头部
            removeNode(node);
            addToHead(node);
            return;
        }

        // 添加新元素
        DListNode newNode = new DListNode(key, value);
        map.put(key, newNode);

        // 添加到双向链表中来  如果添加到head 淘汰tail 反之同理
        addToHead(newNode);
        size++;
        if (size > capacity) {
            // 淘汰元素
            DListNode result = tail.prev;
            removeNode(result);
            map.remove(result.key);
            size--;
        }

    }

    private void addToHead(DListNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}
